package own.stu.jobgib.playown.alg.solution.dp;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**
 * <li>常见动态规划类型</li>
 * <li>给定长度为N的序列或字符串，要求划分成若干段</li>
 * <li>- 段数不限，或指定K段</li>
 * <li>- 每一段满足一定的性质</li>
 * <li>做法</li>
 * <li>- 类似于序列型动态规划，但是通常要加上段数信息</li>
 * <li>- 一般用mijD]记录前i个元素(元素0~i-1)分成i段的性质，如最小代价</li>
 */
public class DivideType {

    public static void main(String[] args) {
        DivideType d = new DivideType();
        /*System.out.println(d.numDecodings("10"));
        System.out.println(d.numDecodings("12"));
        System.out.println(d.numDecodings("226"));
        System.out.println(d.numDecodings("236"));
        System.out.println(d.numDecodings("0226"));*/

//        System.out.println(d.numDecodings_II("*"));
//        System.out.println(d.numDecodings_II("1*"));
        //System.out.println(d.numDecodings_II("2*"));
//         System.out.println(d.numDecodings_II("7*9*3*6*3*0*5*4*9*7*3*7*1*8*3*2*0*0*6*"));
        System.out.println(d.numDecodings_II("1*6*7*1*9*6*2*9*2*3*3*6*3*2*2*4*7*2*9*6*0*6*4*4*1*6*9*0*5*9*2*5*7*7*0*6*9*7*1*5*5*9*3*0*4*9*2*6*2*5*7*6*1*9*4*5*8*4*7*4*2*7*1*2*1*9*1*3*0*6*"));
        // System.out.println(d.numDecodings_tmp("1*6*7*1*9*6*2*9*2*3*3*6*3*2*2*4*7*2*9*6*0*6*4*4*1*6*9*0*5*9*2*5*7*7*0*6*9*7*1*5*5*9*3*0*4*9*2*6*2*5*7*6*1*9*4*5*8*4*7*4*2*7*1*2*1*9*1*3*0*6*"));
    }

    /**
     * 91. 解码方法
     * 一条包含字母 A-Z 的消息通过以下映射进行了 编码 ：
     * <p>
     * 'A' -> "1"
     * 'B' -> "2"
     * ...
     * 'Z' -> "26"
     * 要 解码 已编码的消息，所有数字必须基于上述映射的方法，反向映射回字母（可能有多种方法）。例如，"11106" 可以映射为：
     * <p>
     * "AAJF" ，将消息分组为 (1 1 10 6)
     * "KJF" ，将消息分组为 (11 10 6)
     * 注意，消息不能分组为  (1 11 06) ，因为 "06" 不能映射为 "F" ，这是由于 "6" 和 "06" 在映射中并不等价。
     * <p>
     * 给你一个只含数字的 非空 字符串 s ，请计算并返回 解码 方法的 总数 。
     * <p>
     * 题目数据保证答案肯定是一个 32 位 的整数。
     * <p>
     * 示例 1：
     * 输入：s = "12"
     * 输出：2
     * 解释：它可以解码为 "AB"（1 2）或者 "L"（12）。
     */
    public int numDecodings(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }
        int n = s.length();
        /*
        dp[i] 表示（0~i)的子串的解码方案
        dp[i - 1] + dp[i -2] && 10 <= s.substring(i-2,i) <= 26
         */
        int[] dp = new int[n];
        if (s.charAt(0) == '0') {
            return 0;
        }
        dp[0] = 1;
        int v = 0;
        char c = ' ';
        for (int i = 1; i < n; i++) {
            c = s.charAt(i);
            if (c >= '1' && c <= '9') {
                dp[i] = dp[i - 1];
            }

            v = (c - '0') + (s.charAt(i - 1) - '0') * 10;
            if (v >= 10 && v <= 26) {
                if (i < 2) dp[i] += 1;
                else dp[i] += dp[i - 2];
            }

        }
        return dp[n - 1];
    }

    /**
     * 279. 完全平方数
     * 给你一个整数 n ，返回 和为 n 的完全平方数的最少数量 。
     * 完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。
     * <p>
     * 示例 1：
     * <p>
     * 输入：n = 12
     * 输出：3
     * 解释：12 = 4 + 4 + 4
     */
    public int numSquares(int n) {
        /*
         *dp[i]表示数字i的 完全平方数 的 最小数量
         * dp[j] (i - j = 一个完全平方数）
         * dp[1]=1
         */
        if (n <= 0) return 0;
        int[] dp = new int[n + 1];
        // 初始值
        dp[0] = 0;
        for (int i = 1; i <= n; i++) {
            dp[i] = Integer.MAX_VALUE;
            for (int k = 1; k * k < i; k++) {
                dp[i] = Math.min(dp[i], dp[i - k * k] + 1);
            }
        }
        return dp[n];
    }

    /**
     * <li>划分性动态规划</li>
     * <li>要求将一个序列或字符串划分成若干满足要求的片段</li>
     * <li>解决方法: 最后一步>最后一段</li>
     * <li>枚举最后一段的起点</li>
     *
     * <li>如果题目不指定段数，用m表示前i个元素分段后的可行性/最值，可行性，方式数: Perfect Squares, Palindrome Partition II</li>
     * <li>如果题目指定段数，用f表示前i个元素分成段后的可行性/最值，可行性，方式数: Copy Books</li>
     */
    private void s() {
    }

    /**
     * 437 · 书籍复印
     * 给定n本书，第i本书有pages[i]页。有k个人来抄这些书。
     * 这些书排成一行，每个人都可以索取连续一段的书。例如，一个抄书人可以连续地将书从第i册复制到第j册，但是他不能复制第1册、第2册和第4册（没有第3册）。
     * 他们在同一时间开始抄书，每抄一页书都要花1分钟。为了让最慢的抄书人能在最早的时间完成书的分配，最好的策略是什么？
     * <p>
     * 请返回最慢抄书人花费的最短时间。
     * 书籍页数总和小于等于2147483647
     * <p>
     * 样例
     * 输入: pages = [3, 2, 4], K = 2
     * 输出: 5
     * 解释: 第一个人复印前两本书, 耗时 5 分钟. 第二个人复印第三本书, 耗时 4 分钟.
     */
    public int copyBooks(int[] pages, int K) {
        if (pages == null || pages.length == 0 || K < 0) {
            return Integer.MAX_VALUE;
        }

        int n = pages.length;

        if (n <= K) {
            int ans = Integer.MIN_VALUE;
            for (int page : pages) {
                ans = Math.max(ans, page);
            }
            return ans;
        }

        /*
        dp[K][i]表示前k个人抄写前i本书的最短时间
        前j(j<=i)本书 被前k-1个人抄写，k抄写 pages[j...i-1]
        dp[K][i] = min(max(dp[K - 1][j], pages[j] + ...pages[i - 1]))(j = 0...i)
        初始值
        dp[0][0] = 0 0个人抄写0本书
        dp[0][i] = Integet.MAX, 0个人抄写i本书
        dp[i][0]= 0 i个人抄写0本书
         */
        int[][] dp = new int[K + 1][n];
        Arrays.fill(dp[0], Integer.MAX_VALUE);
        dp[0][0] = 0;

        for (int i = 1; i <= K; i++) {
            for (int j = 1; j <= n; j++) {
                dp[i][j] = Integer.MAX_VALUE;
                int sum = 0;
                for (int a = j; a >= 0; a--) {
                    dp[i][j] = Math.min(dp[i][j], Math.max(dp[i - 1][j], sum));
                    if (j > 0)
                        sum += pages[j - 1];
                }
            }
        }
        return dp[K][n];
    }

    /**
     * 873. 最长的斐波那契子序列的长度
     * 如果序列 X_1, X_2, ..., X_n 满足下列条件，就说它是 斐波那契式 的：
     * <p>
     * n >= 3
     * 对于所有 i + 2 <= n，都有 X_i + X_{i+1} = X_{i+2}
     * 给定一个严格递增的正整数数组形成序列 arr ，找到 arr 中最长的斐波那契式的子序列的长度。如果一个不存在，返回  0 。
     * <p>
     * （回想一下，子序列是从原序列 arr 中派生出来的，它从 arr 中删掉任意数量的元素（也可以不删），而不改变其余元素的顺序。例如， [3, 5, 8] 是 [3, 4, 5, 6, 7, 8] 的一个子序列）
     * <p>
     * 示例：
     * 输入: arr = [1,2,3,4,5,6,7,8]
     * 输出: 5
     * 解释: 最长的斐波那契式子序列为 [1,2,3,5,8] 。
     */
    public int lenLongestFibSubseq(int[] A) {
        if (A == null || A.length < 3) {
            return 0;
        }
        int n = A.length;
        /*

        dp[i][j] 定义二维数组 dp 表示以每个下标对的元素作为最后两个数字的斐波那契子序列的最大长度
        dp[i][j]
        1： max (dp[j][k] + 1, 3) 0 <= k < j, 因为数组是单调递增的，所以a[i] > a[j] > a[k],
        如果（j,k) 是一个序列,呢么dp[j][k] >= 3, 此时只需要加上 数组i, 如果不是一个序列那么 i,j,k 三个组成一个序列
        2：0 （k < 0 || k >= j)
         */
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < A.length; i++) {
            map.put(A[i], i);
        }
        int[][] dp = new int[n][n];
        int max = 0;
        for (int i = 2; i < n; i++) { //至少有3个数字，那么 （i，j,k ）i 需要从下边2开始计算
            for (int j = i - 1; j >= 0 && A[j] * 2 > A[i]; j--) { // a[j] * 2 是为了剪枝，严格递增的序列A, 如果A[j] < A[i]/2,那么 比A[j]小的A[k] 在继续处理也没有意思
                int kIdx = map.getOrDefault(A[i] - A[j], -1);
                if (kIdx == -1) {
                    continue; // 说明 a[k]不在数组A中，（i，j,k)组不成一个小序列
                }
                // 这里不需要考虑 kIdx >= j ,因为严格递增序列，这个条件A[j] * 2 > A[i]已经剔除了这种情况
                dp[i][j] = Math.max(dp[j][kIdx] + 1, 3);
                max = Math.max(max, dp[i][j]);
            }
        }
        return max;
    }

    public int numDecodings_tmp(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }

        final int mod = 1000000007;
        int n = s.length();
        int[] f = new int[n + 1];
        f[0] = 1;
        for (int i = 1; i <= n; i++) {
            f[i] = 0;
            if (s.charAt(i - 1) == '*') {
                f[i] = (int) ((f[i] + 9L * f[i - 1]) % mod);
                if (i >= 2) {
                    if (s.charAt(i - 2) == '*') {
                        f[i] = (int) ((f[i] + 15L * f[i - 2]) % mod);
                    } else if (s.charAt(i - 2) == '1') {
                        f[i] = (int) ((f[i] + 9L * f[i - 2]) % mod);
                    } else if (s.charAt(i - 2) == '2') {
                        f[i] = (int) ((f[i] + 6L * f[i - 2]) % mod);
                    }
                }
            } else {
                if (s.charAt(i - 1) != '0') {
                    f[i] = (f[i] + f[i - 1]) % mod;
                }
                if (i >= 2) {
                    if (s.charAt(i - 2) == '*') {
                        if (s.charAt(i - 1) <= '6') {
                            f[i] = (int) ((f[i] + 2L * f[i - 2]) % mod);
                        } else {
                            f[i] = (f[i] + f[i - 2]) % mod;
                        }
                    } else {
                        int twoDigits = (s.charAt(i - 2) - '0') * 10 + s.charAt(i - 1) - '0';
                        if (twoDigits >= 10 && twoDigits <= 26) {
                            f[i] = (f[i] + f[i - 2]) % mod;
                        }
                    }
                }
            }
        }

        return f[n];
    }

    /**
     * 639. 解码方法 II
     * 一条包含字母 A-Z 的消息通过以下的方式进行了 编码 ：
     * <p>
     * 'A' -> "1"
     * 'B' -> "2"
     * ...
     * 'Z' -> "26"
     * 要 解码 一条已编码的消息，所有的数字都必须分组，然后按原来的编码方案反向映射回字母（可能存在多种方式）。例如，"11106" 可以映射为：
     * <p>
     * "AAJF" 对应分组 (1 1 10 6)
     * "KJF" 对应分组 (11 10 6)
     * 注意，像 (1 11 06) 这样的分组是无效的，因为 "06" 不可以映射为 'F' ，因为 "6" 与 "06" 不同。
     * <p>
     * 除了 上面描述的数字字母映射方案，编码消息中可能包含 '*' 字符，可以表示从 '1' 到 '9' 的任一数字（不包括 '0'）。例如，编码字符串 "1*" 可以表示 "11"、"12"、"13"、"14"、"15"、"16"、"17"、"18" 或 "19" 中的任意一条消息。对 "1*" 进行解码，相当于解码该字符串可以表示的任何编码消息。
     * <p>
     * 给你一个字符串 s ，由数字和 '*' 字符组成，返回 解码 该字符串的方法 数目 。
     * <p>
     * 由于答案数目可能非常大，返回 109 + 7 的 模 。
     * <p>
     * 示例：
     * 输入：s = "*"
     * 输出：9
     * 解释：这一条编码消息可以表示 "1"、"2"、"3"、"4"、"5"、"6"、"7"、"8" 或 "9" 中的任意一条。
     * 可以分别解码成字符串 "A"、"B"、"C"、"D"、"E"、"F"、"G"、"H" 和 "I" 。
     * 因此，"*" 总共有 9 种解码方法。
     */
    public int numDecodings_II(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }
        int n = s.length();

        /*
        dp[i] 前i个字符的解码方法数量
        dp[i] = dp[i - 1](a[i] = 0 ~ 9)
        a[i] = '*'
        dp[i] = dp[i - 1] + 9
        a[i - 1] ( = 1)  dp[i-2] + 9
        a[i - 1] ( = 2)  dp[i-2] + 6
        a[i - 1] ( = '*')dp[i-2] + 15
        看下边的
         */
        long[] dp = new long[n + 1];
        if (s.charAt(0) == '0') {
            return 0;
        }
        dp[0] = 1;
        for (int i = 1; i <= n; i++) {
            dp[i] = 0;
            char c1 = s.charAt(i - 1);
            // 处理1位
            if (c1 >= '1' && c1 <= '9') {
                dp[i] = dp[i - 1];
            }
            if (c1 == '*') {
                dp[i] = dp[i - 1] * 9 % MOD; // * 代表1~9
            }

            // 处理两位
            if (i > 1) {
                char c2 = s.charAt(i - 2);
                // 那么（2位数字） c2 只能表示 1，2
                if (c2 == '1') {
                    if (c1 == '*') {
                        dp[i] += dp[i - 2] * 9 % MOD;
                    } else {
                        dp[i] += dp[i - 2] % MOD;
                    }
                }

                if (c2 == '2') {
                    if (c1 <= '6' && c1 >= '0') {
                        dp[i] += dp[i - 2];
                    } else if (c1 == '*') {
                        dp[i] += dp[i - 2] * 6 % MOD;
                    }
                }

                if (c2 == '*') {
                    if (c1 <= '6' && c1 >= '0') {
                        dp[i] += dp[i - 2] * 2 % MOD;
                    } else if (c1 <= '9' && c1 >= '7') {
                        dp[i] += dp[i - 2];
                    } else {
                        dp[i] += dp[i - 2] * 15 % MOD;
                    }
                }
            }
        }

        return (int) (dp[n] % MOD);
    }

    private int MOD = 1000000007;
}
